#include<stdio.h>
#include<iostream>
using namespace std;

//如何寻找特定遍历序列中二叉树结点的前驱和后继?
//利用二叉链表中的空指针域:
// 		如果某个结点的左孩子为空,则将空的左孩子指针域 改为 指向其前驱; 
// 		如果某个结点的右孩子为空,则将空的右孩子指针域改为指向其后继; 
//	这种改变指向的指针被称为"线索"
//  加上了线索的二叉树称为 线索二叉树(Threaded Binary Tree) 
//  对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化  

//为区分lrchild和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，
//	 对二叉链表中的每个结点增设两个标志域 ltag 和 rtag, 并约定：
//	 ltag = 0 lchild指向该结点的左孩子
//	 ltag = 1 lchild指向该结点的前驱
//   rtag = 0 rchild指向该结点的右孩子 
//   rtag = 1 rchild指向该结点的后继 

#define TElemType int
typedef struct BiTree{
	TElemType data;
	int ltag, rtag; //两个标志域 
	struct BiTree *lchild, *rchild;
}BiTNode, *BiTree;


//带头结点的线索二叉树 
//为避免最后有两个结点指针为悬空态，增设一个头结点 
//该头结点data域为空，ltag = 0,lchild指向根节点
//  				  rtag = 1.rchild指向遍历序列中的 最后一个结点 
//		遍历序列中第一个结点的lchild 域和最后一个结点的rchild 域都指向头结点